package org.xi.dsaa.collection;

/**
 * 双向链表
 *
 * @param <E> 元素类型
 */
public class DoubleLinkedList<E> {

    public DoubleLinkedList() {
    }

    public DoubleLinkedList(E... items) {
        pushAll(items);
    }

    transient int size = 0;
    transient Node<E> first;
    transient Node<E> last;

    public void push(E item) {
        if (size == 0) {
            first = last = new Node<>(item);
            size++;
            return;
        }
        final Node<E> oldLast = last;
        last = new Node<>(item, oldLast, null);
        oldLast.next = last;
        size++;
    }

    public void pushAll(E... items) {
        for (E item : items) {
            push(item);
        }
    }

    public int size() {
        return size;
    }

    private Node<E> getNode(int index) {
        if (index >= size || index < 0) {
            throw new IndexOutOfBoundsException("索引越界");
        }

        Node<E> cursor = first;
        for (int i = 0; i < index; i++) {
            cursor = cursor.next;
        }
        return cursor;
    }

    public void insertAfter(int index, E item) {
        if (size == 0) {
            if (index != 0) {
                throw new IndexOutOfBoundsException("索引越界");
            }
            push(item);
            return;
        }

        Node<E> cursor = getNode(index);
        Node<E> next = cursor.next;
        cursor.next = new Node<>(item, cursor, next);
        if (next != null) {
            next.prev = cursor.next;
        } else {
            last = cursor.next;
        }
        size++;
    }

    public void insertBefore(int index, E item) {
        if (size == 0) {
            if (index != 0) {
                throw new IndexOutOfBoundsException("索引越界");
            }
            push(item);
            return;
        }

        Node<E> cursor = getNode(index);
        Node<E> prev = cursor.prev;
        cursor.prev = new Node<>(item, prev, cursor);
        if (prev != null) {
            prev.next = cursor.prev;
        } else {
            first = cursor.prev;
        }
        size++;
    }

    public void delete(int index) {
        Node<E> cursor = getNode(index);
        Node<E> next = cursor.next;
        Node<E> prev = cursor.prev;
        if (next == null && prev == null) {
            first = last = null;
        } else if (next == null) {
            last = prev;
            prev.next = null;
        } else if (prev == null) {
            first = next;
            next.prev = null;
        } else {
            prev.next = next;
            next.prev = prev;
        }
        size--;
    }

    public void print() {
        Node<E> cursor = first;
        while (cursor != null) {
            System.out.print(cursor.item);
            System.out.print(", ");
            cursor = cursor.next;
        }
        System.out.println();
    }

    private static class Node<E> {
        private E item;
        private Node<E> prev;
        private Node<E> next;

        public Node(E item) {
            this(item, null, null);
        }

        public Node(E item, Node<E> prev, Node<E> next) {
            this.item = item;
            this.prev = prev;
            this.next = next;
        }
    }


    public static void main(String[] args) {
        DoubleLinkedList<Integer> list = new DoubleLinkedList<>(1, 2, 3, 4);
        list.push(100);
        list.print();
        list.delete(3);
        list.print();
        list.delete(0);
        list.print();
        list.insertAfter(1, 20);
        list.insertAfter(1, 20);
        list.print();
        list.insertBefore(1, 20);
        list.insertBefore(1, 20);
        list.print();
        System.out.println(list.size());
    }
}
